#include <bits/stdc++.h>
#include <string>
using namespace std;

struct ListNode
{
    int data;         // 整数
    struct ListNode *next; // 指向下一个结构体的指针(地址)
};

/** 获取链表l的长度 */
int getListLength(const struct ListNode* l){
    int len = 0;
    while(l!=NULL){
     len++;
     l = l->next;
    }
    return len;
}

/**
 * 向链表里插入一个新节点
 * @参数 l 往链表l里插入节点
 * @参数 index 往链表的第index位插入数据
 * @参数 val： 插入一个整数val
 */
struct ListNode *insertList(struct ListNode *l, int index, int val)
{
    struct ListNode *p = l;
    if (index < 0)
        return l;
    // 创建一个节点结构体指针 malloc
    struct ListNode *n = (struct ListNode *)malloc(sizeof(struct ListNode));
    n->data = val;
    n->next = NULL;
    if (index == 0)
    { // 插在第一个位置
        n->next = l;
        return n;
    }
    else
    { // 插入到中间
        for (int i = 0; i < index - 1; i++)
            l = l->next;
        n->next = l->next;
        l->next = n;
        return p;
    }
}

/** 删除链表l的第index个元素 */
struct ListNode* deleteList(struct ListNode* l,int index){
    struct ListNode* p = l;
    int len = getListLength(l);
    if(index<0||index>=len) return l;
    if(index==0){
      p = l->next;
      free(l);
      return p;
    }else{
      for(int i=0;i<index-1;i++){
        l = l->next;
      }
      p = l->next;
      l->next = p->next;
      free(p);
      return l;
    }
}

/** 获取列表l的第i个元素 */
int getListItem(const struct ListNode* l,int index){
    int val = 0,len = getListItem(l);
    if(index<0||index>=len) return NAN;
    for(int i=0;i<index;i++){
      l = l->next;
    }
    return l->data;
}

/** 顺序打印链表l里的每个整数 */
void printList(const struct ListNode *l)
{
    while (l != NULL)
    {
        cout << l->data << " ";
        l = l->next;
    }
    cout << endl;
}

int main()
{

    // 创建一个空链表
    struct ListNode *list = NULL; // 1 2 4
    list = insertList(list, 0, 1);
    list = insertList(list, 1, 2);
    list = insertList(list, 2, 4);
    printList(list);
    list = deleteList(list,1);
    printList(list);
    return 0;
}